use std::collections::VecDeque;

struct ListEntry {
    data: Box<dyn std::any::Any>,
    next: Option<Box<ListEntry>>,
}

impl ListEntry {
    fn new(data: Box<dyn std::any::Any>) -> Self {
        ListEntry { data, next: None }
    }
}

pub struct LinkedList {
    head: Option<Box<ListEntry>>,
    tail: Option<*mut ListEntry>,
    length: usize,
}

impl LinkedList {
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            length: 0,
        }
    }

    pub fn append(&mut self, data: Box<dyn std::any::Any>) {
        let new_entry = Box::new(ListEntry::new(data));
        if let Some(tail) = self.tail.take() {
            unsafe { (*tail).next = Some(new_entry); }
        } else {
            self.head = Some(new_entry);
        }
        self.tail = Some(Box::leak(new_entry.as_mut()));
        self.length += 1;
    }

    pub fn prepend(&mut self, data: Box<dyn std::any::Any>) {
        let new_entry = Box::new(ListEntry { data, next: self.head.take() });
        self.head = Some(new_entry);
        if self.tail.is_none() {
            self.tail = self.head.as_deref_mut().map(|entry| &mut **entry);
        }
        self.length += 1;
    }

    pub fn free(&mut self) {
        while let Some(entry) = self.head.take() {
            self.head = entry.next;
        }
        self.tail = None;
        self.length = 0;
    }

    pub fn next(&self, current: &ListEntry) -> Option<&ListEntry> {
        current.next.as_deref()
    }

    pub fn nth_entry(&self, index: usize) -> Option<&ListEntry> {
        let mut current = self.head.as_ref();
        for _ in 0..index {
            if let Some(entry) = current {
                current = entry.next.as_deref();
            } else {
                return None;
            }
        }
        current
    }

    pub fn nth_data(&self, index: usize) -> Option<&dyn std::any::Any> {
        self.nth_entry(index).map(|entry| &*entry.data)
    }

    pub fn length(&self) -> usize {
        self.length
    }

    pub fn remove_entry(&mut self, entry: Box<ListEntry>) -> Option<Box<dyn std::any::Any>> {
        let mut current = &mut self.head;
        while let Some(ref mut next_entry) = *current {
            if next_entry as *const _ == &*entry {
                *current = entry.next.take();
                if current.is_none() {
                    self.tail = None;
                }
                self.length -= 1;
                return Some(entry.data);
            } else {
                current = &mut next_entry.next;
            }
        }
        None
    }

    pub fn remove_data(&mut self, data: &dyn std::any::Any) -> Option<Box<dyn std::any::Any>> {
        let mut current = &mut self.head;
        while let Some(ref mut entry) = *current {
            if entry.data.type_id() == data.type_id() && entry.data.downcast_ref::<_>() == Some(data) {
                *current = entry.next.take();
                if current.is_none() {
                    self.tail = None;
                }
                self.length -= 1;
                return Some(entry.data);
            } else {
                current = &mut entry.next;
            }
        }
        None
    }

    pub fn sort(&mut self, compare: impl FnMut(&dyn std::any::Any, &dyn std::any::Any) -> std::cmp::Ordering) {
        let mut entries: Vec<_> = self.drain().collect();
        entries.sort_by(compare);
        for entry in entries.into_iter().rev() {
            self.prepend(entry);
        }
    }

    pub fn find_data(&self, data: &dyn std::any::Any) -> Option<&ListEntry> {
        let mut current = self.head.as_ref();
        while let Some(entry) = current {
            if entry.data.type_id() == data.type_id() && entry.data.downcast_ref::<_>() == Some(data) {
                return Some(entry);
            }
            current = entry.next.as_deref();
        }
        None
    }

    pub fn to_array(&self) -> Vec<Box<dyn std::any::Any>> {
        let mut array = Vec::with_capacity(self.length);
        let mut current = self.head.as_ref();
        while let Some(entry) = current {
            array.push(entry.data.clone());
            current = entry.next.as_deref();
        }
        array
    }

    pub fn iterate(&self) -> ListIterator {
        ListIterator { current: self.head.as_ref() }
    }

    fn drain(&mut self) -> Vec<Box<ListEntry>> {
        let mut entries = Vec::new();
        while let Some(entry) = self.head.take() {
            self.head = entry.next;
            entries.push(entry);
        }
        self.tail = None;
        self.length = 0;
        entries
    }
}

pub struct ListIterator<'a> {
    current: Option<&'a ListEntry>,
}

impl<'a> Iterator for ListIterator<'a> {
    type Item = &'a ListEntry;

    fn next(&mut self) -> Option<Self::Item> {
        let entry = self.current;
        if let Some(entry) = entry {
            self.current = entry.next.as_deref();
        }
        entry
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_linked_list() {
        let mut list = LinkedList::new();
        list.append(Box::new(1));
        list.append(Box::new(2));
        list.prepend(Box::new(0));

        assert_eq!(list.length(), 3);
        assert_eq!(*list.nth_data(0).unwrap().downcast_ref::<i32>().unwrap(), 0);
        assert_eq!(*list.nth_data(1).unwrap().downcast_ref::<i32>().unwrap(), 1);
        assert_eq!(*list.nth_data(2).unwrap().downcast_ref::<i32>().unwrap(), 2);

        list.remove_entry(list.head.take().unwrap());
        assert_eq!(list.length(), 2);
        assert_eq!(*list.nth_data(0).unwrap().downcast_ref::<i32>().unwrap(), 1);
        assert_eq!(*list.nth_data(1).unwrap().downcast_ref::<i32>().unwrap(), 2);

        list.remove_data(&2);
        assert_eq!(list.length(), 1);
        assert_eq!(*list.nth_data(0).unwrap().downcast_ref::<i32>().unwrap(), 1);

        list.free();
        assert_eq!(list.length(), 0);
    }
}
